package leetCode.fourthWeek;

import org.junit.Ignore;
import org.junit.Test;

public class Code_76 {
  @Test
  public void test() {}

  //  @Ignore
  public String minWindow(String s, String t) {
    if (!contain(s, t)) {
      return "";
    }
    if (s.length() == 1) {
      return s;
    }

    int length = Integer.MAX_VALUE,
        pStart = 0,
        pEnd = s.length() - 1,
        resStart = 0,
        resEnd = s.length() - 1;
    for (int i = 0; i < s.length(); i++) {
      if (contain(t, "" + s.charAt(i))) { // 找到起点
        pStart = i;
        resStart = i;
        break;
      }
    }

    for (int i = s.length() - 1; i >= 0; i--) { // 找到终点
      if (contain(t, "" + s.charAt(i))) {
        pEnd = i;
        resEnd = i;
        break;
      }
    }

    //    if (resStart == resEnd) {
    //      return "" + s.charAt(resStart);
    //    }

    for (int i = pStart; i <= pEnd; i++) {
      for (int j = pEnd + 1; j > i; j--) {
        if (!isIn(t, s.charAt(i)) || !isIn(t, s.charAt(j - 1))) {
          continue;
        }
        if (contain(s.substring(i, j), t)) {
          if (j - i < length) {
            length = j - i;
            resStart = i;
            resEnd = j;
          }
        } else {
          break;
        }
      }
    }

    return s.substring(resStart, resEnd);
  }

  private Boolean isIn(String s, char i) {
    for (int j = 0; j < s.length(); j++) {
      if (s.charAt(j) == i) {
        return true;
      }
    }
    return false;
  }

  /** 判断s是否包含t */
  //  @Ignore
  private Boolean contain(String s, String t) {
    //    System.out.println("判断开始:" + System.currentTimeMillis());
    if (t.length() == 0 | s.length() == 0 | s.length() < t.length()) {
      return false;
    }
    int[] map = new int[s.length()];
    for (int i = 0; i < t.length(); i++) {
      int j = s.indexOf(t.charAt(i));
      int k = map.length - 1;
      while (k >= 0 && map[k] != 1) {
        k--;
      }
      for (; k >= 0; k--) {
        if (s.charAt(k) == t.charAt(i) && map[k] == 1) {
          j = s.substring(k).indexOf(t.charAt(i)) + k;
          break;
        }
      }

      if (j < 0) {
        return false;
      }
      if (map[j] == 1) {
        if (j == s.length() - 1) {
          return false;
        }
        int jTmp = s.substring(j + 1).indexOf(t.charAt(i));
        if (jTmp < 0) {
          return false;
        } else {
          j = j + 1 + jTmp;
        }
      }
      map[j] = 1;
    }
    return true;
  }
}
